home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / qsortnet.cq / qsortnet.c
Encoding:
Text File  |  1985-11-20  |  3.7 KB  |  193 lines
  1. Article 2718 (12 more) in net.sources:
  2. From: duane@anasazi.UUCP (Duane Morse)
  3. Subject: qsort source
  4. Message-ID: <276@anasazi.UUCP>
  5. Date: 29 Aug 85 14:04:07 GMT
  6. Date-Received: 2 Sep 85 06:12:20 GMT
  7. Distribution: net
  8. Organization: Anasazi, Phoenix Az.
  9. Lines: 182
  10.  
  11. --MORE--(14%)Here is my own version of qsort for those of you interested in sorting
  12. algorithms.
  13. --------------------SUBROUTINE FOLLOWS, THEN MY SIGNATURE -------------
  14. /*TITLE pqsort.c - quicksort algorithm 1/10/85 10:04:32 */
  15.  
  16. static char *version = "@(#)pqsort.c    1.1 1/10/85 10:04:32";
  17.  
  18. /*
  19. ** void pqsort(vec, nel, esize, compptr)
  20. **
  21. **  Quick Sort routine.
  22. **  Based on Knuth's ART OF COMPUTER PROGRAMMING, VOL III, pp 114-117.
  23. **  For some unknown reason, this works faster than the library's qsort.
  24. **
  25. ** Parameters:
  26. **  vec = points to beginning of structure to sort.
  27. **  nel = number of elements.
  28. **  esize = size of an element.
  29. **  compptr = points to the routine for comparing two elements.
  30. **
  31. ** Returns:
  32. **  Nothing.
  33. */
  34.  
  35. static int elsize;              /* Element size */
  36. static int (*comp)();           /* Address of comparison routing */
  37.  
  38. static void memexch(), mysort();
  39.  
  40. void pqsort(vec, nel, esize, compptr)
  41.  
  42. unsigned char *vec;
  43. int nel;
  44. int esize;
  45. int (*compptr)();
  46.  
  47. {
  48.   /* If less than 2 items, done */
  49.   if (nel < 2)
  50.     return;
  51.  
  52.   elsize = esize;
  53.   comp = compptr;
  54.  
  55.   /* Call the real worker */
  56.   mysort(vec, nel);
  57. }
  58. /*PAGE*/
  59. /*
  60. ** void mysort(vec, nel)
  61. **
  62. **  The real quick sort routine.
  63. **
  64. ** Parameters:
  65. **  vec = points to beginning of structure to sort.
  66. **  nel = number of elements.
  67. **
  68. **  esize = size of an element.
  69. **  compptr = points to the routine for comparing two elements.
  70. **
  71. ** Returns:
  72. **  Nothing.
  73. */
  74.  
  75. static void mysort(vec, nel)
  76.  
  77. unsigned char *vec;
  78. int nel;
  79.  
  80. {
  81.   register short i, j;
  82.   register unsigned char *iptr, *jptr, *kptr;
  83.  
  84.   /*
  85.   ** If 2 items, check them by hand.
  86.   */
  87.  
  88. begin:
  89.   if (nel == 2) {
  90.     if ((*comp)(vec, vec + elsize) > 0)
  91.       memexch(vec, vec + elsize, elsize);
  92.     return;
  93.   }
  94.  
  95.   /*
  96.   ** Initialize for this round.
  97.   */
  98.  
  99.   j = nel;
  100.   i = 0;
  101.   kptr = vec;
  102.   iptr = vec;
  103.   jptr = vec + elsize * nel;
  104. /*PAGE*/
  105.   while (--j > i) {
  106.  
  107.     /*
  108.     ** From the righthand side, find the first value that should be
  109.     ** to the left of k.
  110.     */
  111.  
  112.     jptr -= elsize;
  113.     if ((*comp)(jptr, kptr) > 0)
  114.       continue;
  115.  
  116.     /*
  117.     ** Now from the lefthand side, find the first value that should be
  118.     ** to the right of k.
  119.     */
  120.  
  121.     iptr += elsize;
  122.     while(++i < j && (*comp)(iptr, kptr) <= 0)
  123.       iptr += elsize;
  124.  
  125.     if (i >= j)
  126.       break;
  127.  
  128.     /*
  129.     ** Exchange the two items.
  130.     ** k will eventually end up between them.
  131.     */
  132.  
  133.     memexch(jptr, iptr, elsize);
  134.   }
  135.  
  136.   /*
  137.   ** Move item 0 into position.
  138.   */
  139.  
  140.   memexch(vec, iptr, elsize);
  141.  
  142.   /*
  143.   ** Now sort the two partitions.
  144.   */
  145.  
  146.   if ((nel -= (i + 1)) > 1)
  147.     mysort(iptr + elsize, nel);
  148.  
  149.   /*
  150.   ** To save a little time, just start the routine over by hand.
  151.   */
  152.  
  153.   if (i > 1) {
  154.     nel = i;
  155.     goto begin;
  156.   }
  157. }
  158. /*PAGE*/
  159. /*
  160. ** memexch(s1, s2, n)
  161. **
  162. **  Exchange the contents of two vectors.
  163. **
  164. ** Parameters:
  165. **  s1 = points to one vector.
  166. **  s2 = points to another vector.
  167. **  n = size of the vectors in bytes.
  168. **
  169. ** Returns:
  170. **  Nothing.
  171. */
  172.  
  173. static void memexch(s1, s2, n)
  174.  
  175. register unsigned char *s1;
  176. register unsigned char *s2;
  177. register int n;
  178.  
  179. {
  180.   register unsigned char c;
  181.  
  182.   while (n--) {
  183.     c = *s1;
  184.     *s1++ = *s2;
  185.     *s2++ = c;
  186.   }
  187. }
  188. ------------------------------------------------------
  189. -- 
  190.  
  191. Duane Morse     ...!noao!terak!anasazi!duane
  192. (602) 275-0302
  193.